/*
 * @Author: liusheng
 * @Date: 2022-05-07 17:26:31
 * @LastEditors: liusheng
 * @LastEditTime: 2022-05-07 17:54:36
 * @Description: 剑指 Offer II 059. 数据流的第 K 大数值
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 */

#include "header.h"

/*
use multiset to keep at most k element value in order
*/
class KthLargest {
public:
    KthLargest(int k, vector<int>& nums):kth(k),nums_(nums.begin(),nums.end()) {
        int n = nums.size();
        int eraseNum = n - k;
        //erase the num small then the k'th
        if (eraseNum > 0)
        {
            auto iter = nums_.begin();
            advance(iter,eraseNum);
            nums_.erase(nums_.begin(),iter);
        }

        // printf("nums_.size():%d\n",nums_.size());
    }
    
    int add(int val) {
        if (nums_.size() < kth)
        {
            nums_.insert(val);
            return *(nums_.begin());
        }
        
        if (val > *(nums_.begin()))
        {
            nums_.insert(val);
            nums_.erase(nums_.begin());
        }

        return *(nums_.begin());
    }
private:
    int kth;
    multiset<int> nums_;
};

/*
use priorityQ to keep at most k element value in order
*/
class KthLargest {
public:
    KthLargest(int k, vector<int>& nums):k(k), priorityQ(nums.begin(),nums.end()) {
        int n = nums.size();
        if (n > k)
        {
            for ( int i = 0; i < n - k; ++i)
            {
                priorityQ.pop();
            }
        } 
    }

    int add(int val)
    {
        priorityQ.push(val);
        if (priorityQ.size() > k)
        {
            priorityQ.pop();
        }

        return priorityQ.top();
    }
private:
    int k;
    priority_queue<int,vector<int>,std::greater<int>> priorityQ;
};

